1. Field of the Invention
The present invention relates generally to quantum cryptography techniques and, more particularly, to a method for testing the security of a quantum cryptographic system used for quantum key distribution.
2. Prior Art
Current cryptography techniques can be broadly divided into xe2x80x9ccomputationally securexe2x80x9d and xe2x80x9cunconditionally securexe2x80x9d varieties. Computationally secure cryptography is theoretically breakable, but is difficult to break in practice due to the huge amount of time that would be required with existing computer capabilities. On the other hand, unconditionally secure cryptography is impossible to break no matter how much computer power is available, and the existence of unconditionally secure cryptography is proved by Shannon""s information theory.
A typical form of unconditionally secure cryptography is Vernam cryptography, which is implemented by the following procedure. A cryptographic key, which is a random sequence of n bits {0,1}n, is shared between the sending and receiving parties. This key is used only once, and is then discarded (one-time pad method). The sending party converts the plaintext to be conveyed to the receiving party by cryptographic communication into a binary number (consisting of n bits). The cryptographic text (n bits) is obtained as the exclusive-OR (bitwise parity) of the plaintext with the cryptographic key. The resulting cryptographic text is sent to the receiving party. The receiving party obtains the bitwise exclusive-OR of the received cryptographic text with the key. The result is the plaintext expressed as a binary number.
Since a random sequence of data with absolutely no regularity is used as the key, it is essentially impossible to break the cryptographic text without obtaining the key itself, and since the key is only used once before being discarded, it is impossible to gain any information from the cryptographic text.
The quantum key distribution method is currently the only known method whereby shared keys necessary for the implementation of unconditionally secure cryptography in this way can be produced securely between sending and receiving parties at remote locations. The unconditional security of this key distribution method has been proven based on the uncertainty principle of quantum mechanics, which states that any eavesdropping activities made by an eavesdropper will always leave some form of trace in a quantum-level signal.
Quantum key distribution methods that have hereto before been proposed include four-state protocol (commonly referred to as the xe2x80x9cBB84xe2x80x9d protocol), two-particle interference protocol, non-orthogonal two-state protocol, and orthogonal two-state protocol. The BB84 protocol is summarized below. For a detailed description, see C. H. Bennett and G. Brassard, Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India (IEEE, New York, 1984), p. 175.
FIG. 2 illustrates an overview of an apparatus for BB84 protocol, referred to generally by reference numeral 300. Sending party 301, traditionally referred to as xe2x80x9cAlicexe2x80x9d, can produce individual photons with controlled polarization states by operating a transmitter 303 consisting of a single-photon source and a polarization modulator. The individual photons carrying this polarization information constitute carriers for the smallest units of information (quantum bits). Individual photons that have exited from transmitter 303 pass through a quantum channel 305 and arrive at a receiving party 302, traditionally referred to as xe2x80x9cBobxe2x80x9d. Quantum channel 305 might consist of a propagation mode in an optical fiber or in free space. Receiving party 302 measures the state of the individual incoming photons by operating a measuring device 304, which has a controllable measurement basis. This measuring device can be configured from a polarizer and a photon detector, and its measurement basis can be switched by combining it with an electro-optical polarization rotating element such as a Pockels cell. A classical public channel 306 is used when collating the transmitted and received results to test for an eavesdropper 308, traditionally referred to as xe2x80x9cEvexe2x80x9d. Classical public channel 306 might be a radio or telephone link, and although there is no way of telling if it is subjected to eavesdropping, it is assumed that the content of this channel is not falsified.
A description of the BB84 protocol and its basic principles will now be discussed with reference to FIG. 3. A single bit of information, either a logical 0 or a logical 1, is transmitted by using the polarization state of a single photon. A coding method is prearranged between sending party 301 and receiving party 302, an example of which is as follows.
Two types of bases 400, 402 are used: the set {|0 greater than +,|1 greater than +} of linear polarization along horizontal and vertical polarization axes (referred to hereinafter as the plus (+) basis), and the set {|0 greater than x,|1 greater than x} of linear polarization along polarization axes inclined at xc2x145xc2x0 to the horizontal axis (referred to hereinafter as the cross (x) basis). The states |0 greater than + and |0 greater than x are used to represent a logical 0, and the states |1 greater than + and |1 greater than x are used to represent a logical 1. Since four quantum states {|0 greater than +,|1 greater than +,|0 greater than x,|1 greater than x} of individual photons are used in this way, it is referred to as four-state protocol.
A measuring device that can discriminate between photons in the |0 greater than + and |1 greater than + states without errors is called a plus basis measuring device. A plus basis measuring device is completely unable to discriminate between the |0 greater than x and |1 greater than x states, and thus produces logical 0 and logical 1 data at random for each state. On the other hand, a measuring device that can discriminate between photons in the |0 greater than x and |1 greater than x states without errors is called a cross basis measuring device. A cross basis measuring device is completely unable to discriminate between the |0 greater than + and |1 greater than + states, and thus produces logical 0 and logical 1 data at random for each state. It is not possible to use these measuring devices to determine which of these four states {0 greater than +,|1 greater than +,|0 greater than x,|1 greater than x} a photon of unknown state is in (according to the uncertainty principle).
The effect of eavesdropping will now be discussed with reference to FIG. 4. One way in which eavesdropping might occur in this process is as follows. An eavesdropper 308 accesses quantum channel 305 and measures the polarization state of a photon. If the eavesdropper has selected a measuring device capable of distinguishing the polarization state (probability xc2xd), the eavesdropper can either perform a non-demolition quantum measurement (cloning), or retransmit a photon with exactly the same quantum state after performing a demolition measurement, and can thereby reliably ascertain the bit value without raising any suspicion. But when the eavesdropper has selected a measuring device that is unable to distinguish between the polarization states (probability xc2xd), the polarization state of the photon is disturbed. When receiving party 302 measures the disturbed photon with a measuring device capable of distinguishing the polarization state before disturbance, the probability of obtaining the same bit value as the sending party is only xc2xd. Accordingly, the probability of eavesdropping activities escaping detection for one bit is 1xe2x88x92(xc2xd) ({fraction (1/2 )})=xc2xe. If s is the number of test bits, the probability that none of the s bit values is made inconsistent despite the eavesdropping activities is (xc2xe)s, and if s is given a large value, the value of (xc2xe)s rapidly approaches zero. Accordingly, if this eavesdropping test is passed, it can be concluded with a probability sufficiently close to 1 that there is no eavesdropper.
Quantum bit transmission and reception protocol will now be explained. For each bit, sending party 301 randomly selects one of the four polarization states {|0 greater than +,|1 greater than +,|0 greater than x,|1 greater than x} and transmits it to the receiving party 302. This is repeated n times. Receiving party 302 measures the polarization states by randomly selecting one of the two measuring devices (the plus basis or cross basis measuring device) for each bit, and sequentially stores the measurement bases and results. When the receiving party has chosen a measuring device capable of reliably discriminating the polarization state of a photon, the bit value detected by receiving party 302 should always match the bit value sent by the sending party 301. When a measuring device that is incapable of discriminating the polarization state is selected, the bit values of the sending party 301 and receiving party 302 will differ with a probability of xc2xd.
Sending party 301 and receiving party 302 use a classical public channel 306 to collate the bases used for each bit without saying whether the measurement results were 1 or 0. This leaves approximately half the bits for which sending party 301 and receiving party 302 used the same bases; bits for which different bases were used are discarded. If there is no eavesdropper 308 and the channel is noiseless, the two resulting series of random numbers should match perfectly.
Sending party 301 and receiving party 302 extract test bits at random from the resulting random number series and check the two bit values against each other for each bit to check that they match. This test is performed for a sufficient number of bits, and if all the bit values match it can be concluded with a probability close to 1 that there is no eavesdropper 308 for the reasons stated above. If it is concluded that there is no eavesdropper 308, the test bits are discarded and the remaining random number series are used as a shared key. But if just one inconsistent bit is detected, it is concluded that an eavesdropper 308 is present and the current communication session is invalidated. Should this situation arise, the session is restarted from scratch after measures have been taken such as checking the quantum channel or switching to another quantum channel 305a. 
The above process allows the sending and receiving parties 301, 302 to obtain a shared key while confirming that there is no eavesdropper 308 resulting in a secure communication. However, as described in detail below, it is impossible to guarantee the secure key distribution with the prior art BB84 protocol since there is no way in which the reliability of the quantum cryptographic apparatus 300 can be confirmed.
Earlier research has produced the following findings regarding the security of quantum key distribution methods and the reliability of apparatus used to conduct such methods.
First, the security of methods other than BB84 protocol will be discussed. As for non-orthogonal two-state protocol and orthogonal two-state protocol, mathematical proofs have not existed until those of the present invention that they are unconditionally secure against all attacks by an eavesdropper 308 of unlimited ability, even if a perfect apparatus 300 is used. They are considered to offer worse security than BB84 protocol offers.
Two-particle interference protocol can only be guaranteed unconditionally secure against all attacks by an eavesdropper 308 of unlimited ability if the assumption that the apparatus 300 is perfect is satisfied. However, its security cannot be guaranteed if the apparatus is imperfect, and it has been shown that dangerous situations may arise in which eavesdroppers 308 cannot be detected.
The Security of BB84 encryption will now be discussed. Since the four states used in the BB84 protocol are highly symmetrical, research into the mathematical proof of its security is highly advanced (the most advanced for all protocols proposed so far).
The following result is already known: If transmitter 303 is perfect, i.e. if single photons having closely regulated polarization states can be reliably produced 100% of the time, then BB84 protocol is unconditionally secure even if quantum channel 305 and/or measuring device 304 have error rates within a certain range of tolerance. A detailed proof of this proposition can be found in D. Mayers, Advances in Cryptology, Proceedings of Crypto 0796, Lecture Notes in Comp. Sci., Vol. 1109, (Springer-Verlag, 1996), p. 343-357, and D. Mayers, Los Alamos preprint archive quant-ph/9802025. Those skilled in the art will appreciate that the strict condition that transmitter 303 is perfect is still imposed here.
Research is also currently under way into proving the proposition, which is expected to be proven correct, that the BB84 protocol is unconditionally secure as long as errors occurring in the entire quantum apparatus 300 including transmitter 303 are tolerable ones.
Note that two approaches can be used to accept that an apparatus has a required security property. The first approach relies on the general confidence we have in a given technology and on the expertise of physicists. The second approach relies on a cryptographic test (typically) executed on each execution of the protocol.
In the first approach, the property must be stated as an assumption. It is not proven. Note that the assumption might require the execution of some regular verifications. For example, an assumption that the error rate is below 2 percent might require that Alice and Bob are not too far away. This kind of verification belongs to the first approach because it does not remove the assumption. We still have to rely on our general confidence in a technology or in the expertise of physicists. This approach is fine to establish as a physical law that privacy is possible, but it is not acceptable for a cryptographic purpose. The problem is that in a particular execution, the apparatus might be defective, or perhaps the manufacturer was not careful, and the assumption might turn out to be wrong.
The second approach uses a test together with some basic assumptions (which are not proven) and it actually proves the desired property (under the stated assumptions). For example, a test on the error rate can be used to prove that the error rate is below some given level, for instance, 2 percent. In this case, one required assumption is that the tested positions are chosen uniformly at random. The advantage is that the required assumptions are usually easier to verify and accept without a proof than is the desired property itself. This second approach is much more secure and is the one typically used to bound the error rate from above. In this approach, one does not rely on the expertise of physicists to conclude that the error rate is bounded from above.
The present invention supports the second approach but does more than bound the error rate from above. Only an upper bound on the error rate does not guarantee privacy if the quantum apparatus is defective. The test associated with the invention proves the complete security of the apparatus.
If the security property of the apparatus is not proven, it has been pointed out that there may be cases where there is a danger that eavesdroppers 308 may go completely undetected. An example of this is illustrated in FIG. 5. It is assumed that a perfect single-photon source 303 always emits just one photon each time, but in the event that a defective source 303a which emits two or more photons {overscore (h)}xcfx89e, {overscore (h)}xcfx89b is used, an eavesdropper 308 can obtain almost all of the information (e.g. by using a beam splitter 600 to steal some of the plurality of photons {overscore (h)}xcfx89e) without any of his activities being detected, which is clearly dangerous. Many other examples having potentially dangerous results such as this are also conceivable as recognized by those skilled in the art.
The details of research into the security of quantum key distribution methods and the reliability of apparatus as discussed above clearly demonstrate that to establish a key with guaranteed security, it is first essential to evaluate the reliability of the overall quantum apparatus 300 consisting of transmitter 303, quantum channel 305 and measuring device 304 (plus a reliability checking apparatus, if required).
However, no methods have hereto before been devised for checking the reliability of the complete set of quantum cryptographic apparatus under comprehensive conditions.
Therefore it is an object of the present invention to provide a method and apparatus which is able to check the reliability of a quantum cryptographic apparatus.
It is a further object of the present invention to provide a method and apparatus which is able to confirm the security of the quantum key distribution.
The present invention provides a technique for quantum key distribution wherein three quanta having a quantum correlation are used as carriers of key information. In a preferred implementation of the present invention, the state of the three quanta having a quantum correlation is a Greenberger-Horne-Zeilinger (GHZ) state represented as
(|0 greater than |0 greater than |0 greater than +|1 greater than |1 greater than |1 greater than )/{square root over (2)}, or
(|0 greater than |0 greater than |0 greater than xe2x88x92|1 greater than |1 greater than |1 greater than )/{square root over (2)}
in a certain two-dimensional orthonormal basis B={|0 greater than ,|1 greater than }. Preferably, the technique of the present invention is such that the sending party produces three quanta having a quantum correlation represented by a GHZ state in a certain two-dimensional orthonormal basis B={|0 greater than ,|1 greater than }, the states of two of these three quanta are measured by the sending party, and the other one is transmitted to the receiving party and its state is measured by the receiving party, and wherein each quantum state measurement is made using either of the following two types of basis: A two-dimensional orthonormal basis Bb={|0 greater than b,|1 greater than b}, where:
|0 greater than b=(|0 greater than +|1 greater than )/{square root over (2)}
|1 greater than b=xe2x88x92i(|0 greater than xe2x88x921 greater than )/{square root over (2)}
A two-dimensional orthonormal basis Bc={|0 greater than c,|1 greater than c}, where:
|0 greater than c={(1xe2x88x92i)|0 greater than +(1+i)|1 greater than }/{square root over (2)}
|1 greater than c={(1+i)|0 greater than +(1xe2x88x92i)|1 greater than }/{square root over (2)}
and wherein, after this procedure has been repeated a plurality of times, the parities of the measurement results are collated by an exchange of information between the sending and receiving parties over a public channel, thereby checking for eavesdroppers and testing the reliability of the apparatus. Preferably, the technique as mentioned above uses photons or electrons or atoms as carriers for the key information. Alternatively, the technique as mentioned above uses a two-dimensional Hilbert space of photon polarization states or electron spin states or nuclear spin states as the signaling space for key information.
Consequently, the methods of the present invention are able to solve the problem of being unable to confirm the security of quantum key distribution. Specifically, the technique of the present invention allows the security of key distribution to be guaranteed because it can confirm the reliability of the quantum apparatus as well as the presence or absence of eavesdropping.
Accordingly, the present invention is directed to a method for testing the reliability of a quantum key distribution apparatus. The method comprises the steps of: producing a set of quanta by a sender, the set of quanta comprising first, second, and third quanta, the first, second, and third quanta having a quantum correlation; measuring the first and second quantum at the sender using one of two prearranged bases; transmitting the third quanta to a receiver over the quantum channel; measuring the third quanta at the receiver using one of the two prearranged bases; and exchanging information regarding the measured bases between the sender and receiver over a public channel to check for a known behavior of the quantum apparatus based upon the quantum correlation, wherein if the quantum apparatus behaves as is known or within a tolerable limit the reliability of the quantum apparatus is confirmed.
Also provided is a method for quantum key distribution. The method comprises the steps of: producing a set of quanta by the sender, the set of quanta comprising first, second, and third quanta for use as carriers of key information, the first, second, and third quanta having a quantum correlation; measuring the first and second quantum at the sender using a randomly selected basis from a group consisting of two bases; transmitting the third quanta to the receiver over the quantum channel; measuring the third quanta at the receiver using a randomly selected basis from a group consisting of the two bases; exchanging information regarding the measured bases between the sender and receiver over a public channel to check for a known behavior of the quantum apparatus based upon the quantum correlation; and reiterating the above steps a plurality of times thereby sharing the key as a string of bits wherein each bit of the string is distributed for each iteration where the quantum apparatus behaves as is known or within a tolerable limit, and where the bit value is determined according to a predetermined criteria based upon the randomly selected basis chosen for the first, second, and third quantum and the measurement thereof.
Apparatus for carrying out the methods of the present invention are also provided.